import java.util.Arrays;

public class Heap {
    public int[] elem;
    public  int size;

    public Heap(int x){
        this.elem = new int[x];
    }

    public void insert(int[] s){
        for(int i=0;i<s.length;i++){
            elem[i] = s[i];
            size++;
        }
    }

    public boolean isFull(){
        return this.size == this.elem.length;
    }

    public void creatHeap(){
        for(int i = (this.size-2);i>=0;i--){
            siftDown(i,size);
        }
    }

    public void swap(int i,int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

    private void siftDown(int parent, int size) {
        int child = parent*2+1;
        while(child<size){
            //找到最大的孩子
            if(child+1<size&&elem[child+1]>elem[child]){
                child++;
            }
            if(elem[child]>elem[parent]){
                swap(child,parent);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }

    public void offer(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[size++] = val;
        siftup(size-1);
    }

    private void siftup(int chlid) {
        while(chlid>0){
            int parent = (chlid-1)/2;
            if(elem[parent]<elem[chlid]){
                swap(parent,chlid);
                chlid = parent;
            }else {
                break;
            }
        }
    }

    public  int poll(){
        swap(this.size-1,0);
        size--;
        siftDown(0,size);
        return elem[size];
    }

    public  int peek(){
        if(size==0){
            return -1;
        }
        return elem[0];
    }

    public void heapSort(){
        int end = size-1;
        while(end>0){
            swap(end,0);
            siftDown(0,end);
            end--;
        }
    }
}
